#include <stdio.h>
#include <stdlib.h>
#include "mySearch.h" 

//二叉排序树中插入结点的非递归算法，在根结点root的二叉排序树中插入结点newp 
BSTNode *BSTNode_insert(BSTNode *root,BSTNode *newp)
{
    BSTNode *p=root;
    if(root==NULL)
        return newp;
    while(1)
    {
        if(newp->data<p->data)
        {
            if(p->lch)//左孩子不为空，依次遍历 
                p=p->lch;
            else//左孩子为空，则找到插入的位置 
            {
                p->lch=newp;
                return root;
            }
        }else
        {
            if(p->rch)
                p=p->rch;
            else
            {
                p->rch=newp;
                return root;
            }
        }
    }
} 

//利用二叉排序树的插入算法，建立二叉排序树 
BSTNode *BSTNode_create(BSTNode *root,int a[],int n)
{
    int i; 
    BSTNode *p,*head=NULL;//head头结点，初始为空，p临时结点 
    for(i=0;i<n;i++)
    {
        p=(BSTNode *)malloc(sizeof(BSTNode));//新结点分配内存空间 
        p->data=a[i];//数据域赋值 
        p->lch=NULL;
        p->rch=NULL; //左右孩子为空 
        head=BSTNode_insert(head,p); //调用插入结点函数 
        //printf("%d  ",p->data);
        
    } 
    return head; 
} 

//二叉排序树的查找递归算法 ，在根结点root的二叉排序树中查找关键字为x的结点的地址 
BSTNode *BSTNode_search_recurse(BSTNode *root,int x)
{
    if(root==NULL)
        return NULL;
    else if(x==root->data)
        return root;
    else if(x<root->data)
        return BSTNode_search_recurse(root->lch,x);
    else
        return BSTNode_search_recurse(root->rch,x);
}

//二叉排序树的查找非递归算法，在根结点root的二叉排序树中查找关键字为x的结点的地址 
BSTNode *BSTNode_search(BSTNode *root,int x)
{
    BSTNode *p=root;
    while(p!=NULL)
    {
        if(x==p->data)
            return p;
        else if(x<p->data)
            p=p->lch;
        else
            p=p->rch;            
    } 
    return NULL;
} 

/*中序遍历二叉树，递归实现*/
void inorder(BSTNode *root){
    if(root!=NULL){
    	inorder(root->lch);/*访问左子树*/
		printf("%4d",root->data);/*访问根结点*/
    	inorder(root->rch);/*访问右子树*/
    }
}


 
